Data communications systems comprise data communications equipment and data processing equipment connected together by data transmission links. Information is transmitted over these data transmission links in a serial fashion from one device to another in the form of a stream of information which has an identifiable beginning and end. This serial stream of information contains not only data information which includes the origin and/or destination of the data and information indicating the type of data being conveyed, but also control information which includes information designating the beginning and end of the stream. Before transmission, the data information and the control information are merged together to create a frame, which consists of a data field surrounded by specially coded control symbols.
Bit-oriented data link protocols are a set of predetermined agreements governing the exchange of information. One type of bit-oriented protocol is based on a run-length code which is used to efficiently merge, and subsequently separate, the control information from the data information before and after transmission on the communications link. The run-length of ones is the number of successive ones in a bit stream without any intervening zero. Similarly, the run-length of zeroes is the number of successive zeroes in the bit stream without any intervening one. In a run-length coding scheme, special symbols with large run-length are used as control symbols. A bit stuffing technique is used to ensure that such symbols do not appear in the middle of the data field of the frame. Thus, the run length of ones and zeroes provides a way to distinguish between the control information and the data information received.
A symmetrical run-length code specifies the maximum run length of both ones and zeroes which can occur during the active state of information transmission. Since a symmetrical run-length code guarantees a minimum transition density of ones and zeroes for all data and control streams in the active state, clocking information can be encoded. Note that the limit applies only during the active state. During idle state, there is no upper limit to the run length of ones or zeroes transmitted.
HDLC is also a run-length code. However, it falls into a second class of run-length codes referred to as asymmetrical run-length codes.
Asymmetrical run-length codes are those that specify either a maximum run length of ones or a maximum run length of zeroes in the active, non-idle state. Since asymmetrical run-length codes only guarantee a maximum number of ones in a zero field, or vice versa, they cannot effectively encode clocking information. HDLC limits the number of ones in a zero field. Asymmetrical run-length codes are DC unbalanced.
In HDLC, a control symbol is placed at the beginning and the end of the data stream to indicate to the receiver when a new stream of data begins and to indicate when the stream of data ends. The data stream bounded by the control symbol is called a packet or a frame. The control symbol used to indicate the beginning of the frame is called "starting delimiter." Similarly, an "ending delimiter" is used to indicate the end of the frame. Other control symbols are used to abort frames and change line state. In HDLC, a single control symbol can serve as an ending delimiter for one frame and as a starting delimiter for another frame, and so it is more appropriately called a "frame delimiter." The frame delimiter is defined as a unique pattern of ones and zeroes comprising 01111110--a sequence of six ones preceded and followed by zeroes. The run length of ones in the frame delimiter is six. The receiver recognizes this pattern as control information and operates accordingly. The frame, however, also contains data information in the form of ones and zeroes whose pattern can be entirely arbitrary. Consequently, it is possible that the starting delimiter pattern, 01111110, could appear at any time during the transmission of data information. If the receiver recognizes this pattern as a frame field instead of the data it represents, the data transmission would be destroyed. To prevent this problem, an operation called "bit stuffing" is used.
"Bit stuffing" involves altering the original data stream by placing ("stuffing") a zero bit in the sequence of ones whenever the run length of ones exceeds five. These extra (stuffed) zero bits are removed at the receiver by observing the run length of ones. Whenever a zero follows a sequence of 5 ones, the zero is assumed to be a stuffed bit and is removed. A larger run length of ones is interpreted as a control symbol. Thus, bit stuffing allows the receiver to distinguish data information from control information. The maximum run length could have been set at any other boundary value. This boundary value has been set to five in HDLC.
While useful for delineating the control stream from the data stream, bit stuffing does not account for data errors which are capable of destroying or prematurely terminating a transmission. Consider, for instance, a data sequence including two zeroes, followed by five ones and another zero (i.e., 00111110). If this sequence experiences an error during the transmission which converts the second zero to a one (i.e., 01111110), the device receiving this transmission will recognize it as a frame delimiter control symbol, indicating that the data sequence (frame) has ended or a new data sequence has begun.
Traditional implementations use a checksum or cyclic redundancy check (CRC) to detect such errors. If the checksum that is calculated after reception of the transmitted data does not correspond to the pre-calculated checksum sent with the data, the receiving device attempts to identify and correct the erroneous bit or requests a re-transmission. Unfortunately, the effectiveness of such detection/correction algorithms depends on to the complexity and bit-length of the checksum sequence. HDLC uses a 16-bit CRC. The probability that a falsely created frame delimiter will not be detected by a HDLC CRC is 2.sup.-16 P. Here, P is the probability of a bit error. Since the number of bit errors that result in undetected errors is just one, conventional HDLC framing has a Hamming distance of one. Both the probability of undetected errors and the Hamming distance of HDLC are unacceptable for many high-speed applications where billions of frames are transmitted every day. Thus, there is a need to either strengthen the CRC or use a stronger frame delimiter.